package modele;

import java.util.ArrayList;
import java.util.HashSet;

public class Dijkstra
{
	 static public  int[] Dijkstra( Graphe g , int source )
	 {
		 double dist[] = new double[g.lN.size()];
		 int[] previous = new int[g.lN.size()];
		 
		// Initializations
		 for( int i = 0 ; i < g.lN.size(); i++ )
		 {
			 dist[i] = Double.MAX_VALUE;           // Unknown distance function from source to v
			 previous[i] = -1;    // Previous node in optimal path from source
		 }
		 
		 dist[source] = 0;// Distance from source to source
		 previous[source] = source;
		 
		 HashSet<Noeud> Q = new HashSet<Noeud>();
		 
		 Q.addAll(g.lN);// All nodes in the graph are unoptimized - thus are in Q
	
		 while( Q.size() > 0 ) // The main loop
		 {
			 int u = min( Q , g , dist );

			if( dist[u] == Double.MAX_VALUE )
			{
				break; // all remaining vertices are inaccessible from source
		 	}
			
			Q.remove(g.lN.get(u));

			for( int j = 0 ; j < g.lN.get(u).liens.size() ; j++ )// where v has not yet been removed from Q.
			{
				double alt = dist[u] + g.lN.get(u).liens.get(j).stdDis;
				
				//System.out.println( " alt " + alt );
				if( alt < dist[g.lN.get(u).liens.get(j).dest.num] )// Relax (u,v,a)
				{
					dist[g.lN.get(u).liens.get(j).dest.num] = alt;
					
					previous[g.lN.get(u).liens.get(j).dest.num] = u;
					
				}
			}

		//19                  decrease-key v in Q;       // Reorder v in the Queue
		 };
		
		 return previous;
	 }

	private static int min(HashSet<Noeud> q, Graphe g, double[] dist)
	{
		double vmin = Double.MAX_VALUE;
		int nmin = -1;
		//System.out.println("Debut");
		//System.out.println("Q : " + q.size() );
		
		for( int i = 0 ; i < dist.length ; i++ )
		{
			//System.out.println("v " + dist[i] + " dans q " + q.contains( g.lN.get( i ) ) );
			if( dist[i] < vmin && q.contains( g.lN.get( i ) ) )
			{
				//System.out.println("Selc " + dist[i]);
				vmin = dist[i];
				nmin = i;
			}
		}
		//System.out.println(vmin + " pour " + nmin );
		return nmin;
	}
}
